#/usr/bin/env python

__author__ = 'uli'

## another comment
#####################################################################
# ChessBoard v2.05 is created by John Eriksson - http://arainyday.se
# It's released under the Gnu Public Licence (GPL)
# Have fun! (hmmm, this is not so much fun)
#####################################################################

from copy import deepcopy
from pprint import pprint


# Awesome chessboard comment from Arman and Seamus

# chess is class

class ChessBoard:

    # Color values
    WHITE = 0
    BLACK = 1
    NOCOLOR = -1
    EKERMOOCOLOR = 6

    # Promotion values
    QUEEN = 1
    ROOK = 2
    KNIGHT = 3
    BISHOP = 4

    # Reason values
    INVALID_MOVE = 1
    INVALID_COLOR = 2
    INVALID_FROM_LOCATION = 3
    INVALID_TO_LOCATION = 4
    MUST_SET_PROMOTION = 5
    GAME_IS_OVER = 6
    AMBIGUOUS_MOVE = 7
    
    # Test - Alan
    # Result values
    NO_RESULT = 0
    WHITE_WIN = 1
    BLACK_WIN = 2
    STALEMATE = 3
    FIFTY_MOVES_RULE = 4
    THREE_REPETITION_RULE = 5

    # Special moves
    NORMAL_MOVE = 0
    EP_MOVE = 1
    EP_CAPTURE_MOVE = 2
    PROMOTION_MOVE = 3
    KING_CASTLE_MOVE = 4
    QUEEN_CASTLE_MOVE = 5

    # Text move output type
    AN = 0      # g4-e3
    SAN = 1     # Bxe3
    LAN = 2     # Bg4xe3

    _game_result = 0
    _reason = 0

    # States
    _turn = PINK
    _white_king_castle = True
    _white_queen_castle = True
    _black_king_castle = True
    _black_queen_castle = True
    _board = None
    _ep = [0, 0]      # none or the location of the current en pessant pawn
    _fifty = 0

    _black_king_location = (0, 0)
    _white_king_location = (0, 0)

    # three rep stack
    _three_rep_stack = []

    # full state stack
    _state_stack = []
    _state_stack_pointer = 0
    # random comment
    # all moves, stored to make it easier to build textmoves
    #[piece,from,to,takes,promotion,check/checkmate,specialmove]
    #["KQRNBP",(fx,fy),(tx,ty),True/False,"QRNB"/None,"+#"/None,0-5]
    _cur_move = [None, None, None, False, None, None, 0]
    _moves = []

    _promotion_value = 0

    def __init__(self):
        self.resetBoard()

    def state2str(self):

        b = ""
        for l in self._board:
            b += "%s%s%s%s%s%s%s%s" % (l[0], l[1], l[2],  l[3], l[4], l[5], l[6], l[7])

        d = (b,
        self._turn,
        self._white_king_castle,
        self._white_queen_castle,
        self._black_king_castle,
        self._black_queen_castle,
        self._ep[0],
        self._ep[1],
        self._game_result,
        self._fifty)

        #turn,wkc,wqc,bkc,bqc,epx,epy,game_result,fifty
        s = "%s%d%d%d%d%d%d%d%d:%d" % d

        return s

    def loadCurState(self):
        s = self._state_stack[self._state_stack_pointer-1]
        b= s[:64]
        v = s[64:72]
        f =  int(s[73:])

        idx = 0
        for r in range(8):
            for c in range(8):
                self._board[r][c]=b[idx]
                idx+=1

        self._turn                  = int(v[0])
        self._white_king_castle     = int(v[1])
        self._white_queen_castle    = int(v[2])
        self._black_king_castle     = int(v[3])
        self._black_queen_castle    = int(v[4])
        self._ep[0]                 = int(v[5])
        self._ep[1]                 = int(v[6])
        self._game_result           = int(v[7])

        self._fifty = f

    def pushState(self):
        """ My Test Commit """
        if self._state_stack_pointer != len(self._state_stack):
            self._state_stack = self._state_stack[:self._state_stack_pointer]
            self._three_rep_stack =  self._three_rep_stack[:self._state_stack_pointer]
            self._moves = self._moves[:self._state_stack_pointer-1]

        three_state = [self._white_king_castle,
            self._white_queen_castle,
            self._black_king_castle,
            self._black_queen_castle,
            deepcopy(self._board),
            deepcopy(self._ep)]
        self._three_rep_stack.append(three_state)

        state_str = self.state2str()
        self._state_stack.append(state_str)

        self._state_stack_pointer = len(self._state_stack)

    def pushMove(self):
        self._moves.append(deepcopy(self._cur_move))

    def threeRepetitions(self):

        ts = self._three_rep_stack[:self._state_stack_pointer]

        if not len(ts):
            return False

        last = ts[len(ts)-1]
        if(ts.count(last) == 3):
            return True
        return False

    def updateKingLocations(self):
        for y in range(0, 8):
            for x in range(0, 8):
                if self._board[y][x] == "K":
                    self._white_king_location = (x, y)
                if self._board[y][x] == "k":
                    self._black_king_location = (x, y)

    def setEP(self, epPos):
        self._ep[0], self._ep[1] = epPos

    def clearEP(self):
        self._ep[0] = 0
        self._ep[1] = 0

    def endGame(self, reason):
	# dcrm:120312
	print "GAME OVER"
        self._game_result = reason

    def checkKingGuard(self, fromPos, moves, specialMoves={}):
        result = []

        if self._turn == self.WHITE:
            kx, ky = self._white_king_location
        else:
            kx, ky = self._black_king_location

        fx, fy = fromPos

        done = False
        fp = self._board[fy][fx]
        self._board[fy][fx] = "."
        if not self.isThreatened(kx, ky):
            done = True
        self._board[fy][fx] = fp

        if done:
            return moves

        for m in moves:
            tx, ty = m
            sp = None
            fp = self._board[fy][fx]
            tp = self._board[ty][tx]

            self._board[fy][fx] = "."
            self._board[ty][tx] = fp

            if specialMoves.has_key(m) and specialMoves[m] == self.EP_CAPTURE_MOVE:
                sp = self._board[self._ep[1]][self._ep[0]]
                self._board[self._ep[1]][self._ep[0]] = "."

            if not self.isThreatened(kx, ky):
                result.append(m)

            if sp:
                self._board[self._ep[1]][self._ep[0]] = sp

            self._board[fy][fx] = fp
            self._board[ty][tx] = tp

        return result

    def isFree(self, x, y):
        return self._board[y][x] == '.'

    def getColor(self, x, y):
        if self._board[y][x] == '.':
            return self.NOCOLOR
        elif self._board[y][x].isupper():
            return self.WHITE
        elif self._board[y][x].islower():
            return self.BLACK

    def isThreatened(self, lx, ly, player=None):
        """
        Check if a particular square on the board denoted by 
        coords (lx, ly) is under threat by any other piece.
        Returns: True is (lx, ly) is under threat, False if not.
        """

        if player == None:
            player = self._turn

        if player == self.WHITE:
            if lx<7 and ly>0 and self._board[ly-1][lx+1] == 'p':
                return True
            elif lx>0 and ly>0 and self._board[ly-1][lx-1] == 'p':
                return True
        else:
            if lx<7 and ly<7 and self._board[ly+1][lx+1] == 'P':
                return True
            elif lx>0 and ly<7 and self._board[ly+1][lx-1] == 'P':
                return True

        m =[(lx+1, ly+2), (lx+2, ly+1), (lx+2, ly-1), (lx+1, ly-2), (lx-1, ly+2), (lx-2, ly+1), (lx-1, ly-2), (lx-2, ly-1)]
        for p in m:
            if p[0] >= 0 and p[0] <= 7 and p[1] >= 0 and p[1] <= 7:
                if self._board[p[1]][p[0]] == "n" and player==self.WHITE:
                    return True
                elif self._board[p[1]][p[0]] == "N" and player==self.BLACK:
                    return True

        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, 1), (1, -1), (-1, -1)]
        for d in dirs:
            x = lx
            y = ly
            dx, dy = d
            steps = 0
            while True:
                steps+=1
                x+=dx
                y+=dy
                if x<0 or x>7 or y<0 or y>7:
                    break
                if self.isFree(x, y):
                    continue
                elif self.getColor(x, y)==player:
                    break
                else:
                    p = self._board[y][x].upper()
                    if p == 'K' and steps == 1:
                        return True
                    elif p == 'Q':
                        return True
                    elif p == 'R' and abs(dx) != abs(dy):
                        return True
                    elif p == 'B' and abs(dx) == abs(dy):
                        return True
                    break
        return False
    
    ''' Returns True if player has valid moves (conflict resolved)'''
    def hasAnyValidMoves(self, player=None):
        if player == None:
            player = self._turn

        for y in range(0, 8):
            for x in range(0, 8):
                if self.getColor(x, y) == player:
                    if len(self.getValidMoves((x, y))):
                        return True
        return False

    #-----------------------------------------------------------------

    def traceValidMoves(self, fromPos, dirs, maxSteps=8):
        print("hello")
	moves = []
        for d in dirs:
            x, y = fromPos
            dx, dy = d
            steps = 0
            while True:
                x+=dx
                y+=dy
                if x<0 or x>7 or y<0 or y>7:
                    break
                if self.isFree(x, y):
                    moves.append((x, y))
                elif self.getColor(x, y)!=self._turn:
                    moves.append((x, y))
                    break
                else:
                    break
                steps+=1
                if steps == maxSteps:
                    break
        return moves

    def getValidQueenMoves(self, fromPos):
        moves = []
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, 1), (1, -1), (-1, -1) ]

        moves = self.traceValidMoves(fromPos, dirs)

        return self.checkKingGuard(fromPos, moves)

    def getValidRookMoves(self, fromPos):
        moves = []
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        moves = self.traceValidMoves(fromPos, dirs)

        return self.checkKingGuard(fromPos, moves)

    def getValidBishopMoves(self, fromPos):
        moves = []
        dirs = [(1, 1), (-1, 1), (1, -1), (-1, -1) ]

        moves = self.traceValidMoves(fromPos, dirs)

        return self.checkKingGuard(fromPos, moves)

    def getValidPawnMoves(self, fromPos):
        moves = []
        specialMoves = {}
        fx, fy = fromPos

        if self._turn == self.WHITE:
            movedir = -1
            startrow = 6
            ocol = self.BLACK
            eprow = 3
        else:
            movedir = 1
            startrow = 1
            ocol = self.WHITE
            eprow = 4

        if self.isFree(fx, fy+movedir):
            moves.append((fx, fy+movedir))

        if fy == startrow:
            if self.isFree(fx, fy+movedir) and self.isFree(fx, fy+(movedir*2)):
                moves.append((fx, fy+(movedir*2)))
                specialMoves[(fx, fy+(movedir*2))] = self.EP_MOVE
        if fx < 7 and self.getColor(fx+1, fy+movedir) == ocol:
            moves.append((fx+1, fy+movedir))
        if fx > 0 and self.getColor(fx-1, fy+movedir) == ocol:
            moves.append((fx-1, fy+movedir))

        if fy == eprow and self._ep[1] != 0:
            if self._ep[0] == fx+1:
               moves.append((fx+1, fy+movedir))
               specialMoves[(fx+1, fy+movedir)] = self.EP_CAPTURE_MOVE
            if self._ep[0] == fx-1:
               moves.append((fx-1, fy+movedir))
               specialMoves[(fx-1, fy+movedir)] = self.EP_CAPTURE_MOVE

        moves = self.checkKingGuard(fromPos, moves, specialMoves)

        return (moves, specialMoves)

    def getValidKnightMoves(self, fromPos):
        moves = []
        fx, fy = fromPos
        m =[(fx+1, fy+2), (fx+2, fy+1), (fx+2, fy-1), (fx+1, fy-2), (fx-1, fy+2), (fx-2, fy+1), (fx-1, fy-2), (fx-2, fy-1)]
        for p in m:
            if p[0] >= 0 and p[0] <= 7 and p[1] >= 0 and p[1] <= 7:
                if self.getColor(p[0], p[1])!=self._turn:
                    moves.append(p)

        return self.checkKingGuard(fromPos, moves)

    def getValidKingMoves(self, fromPos):
        moves = []
        specialMoves={}

        if self._turn == self.WHITE:
            c_row = 7
            c_king = self._white_king_castle
            c_queen = self._white_queen_castle
            k = "K"
        else:
            c_row = 0
            c_king = self._black_king_castle
            c_queen = self._black_queen_castle
            k = "k"

        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, 1), (1, -1), (-1, -1) ]

        t_moves = self.traceValidMoves(fromPos, dirs, 1)
        moves = []

        self._board[fromPos[1]][fromPos[0]] = '.'

        for m in t_moves:
            if not self.isThreatened(m[0], m[1]):
                moves.append(m)

        if c_king:
            if self.isFree(5, c_row) and self.isFree(6, c_row) and self._board[c_row][7].upper() == 'R':
                if not self.isThreatened(4, c_row) and not self.isThreatened(5, c_row) and not self.isThreatened(6, c_row):
                    moves.append((6, c_row))
                    specialMoves[(6, c_row)] = self.KING_CASTLE_MOVE
        if c_queen:
            if self.isFree(3, c_row) and self.isFree(2, c_row) and self.isFree(1, c_row) and self._board[c_row][0].upper() == 'R':
                if not self.isThreatened(4, c_row) and not self.isThreatened(3, c_row) and not self.isThreatened(2, c_row):
                    moves.append((2, c_row))
                    specialMoves[(2, c_row)] = self.QUEEN_CASTLE_MOVE

        self._board[fromPos[1]][fromPos[0]] = k

        return (moves, specialMoves)

    # -----------------------------------------------------------------------------------

    def movePawn(self, fromPos, toPos):
        moves, specialMoves = self.getValidPawnMoves(fromPos)

        if not toPos in moves:
            return False

        if specialMoves.has_key(toPos):
            t = specialMoves[toPos]
        else:
            t = 0

        if t == self.EP_CAPTURE_MOVE:
            self._board[self._ep[1]][self._ep[0]] = '.'
            self._cur_move[3]=True
            self._cur_move[6]=self.EP_CAPTURE_MOVE

        pv = self._promotion_value
        if self._turn == self.WHITE and toPos[1] == 0:
            if pv == 0:
                self._reason = self.MUST_SET_PROMOTION
                return False
            pc = ['Q', 'R', 'N', 'B']
            p = pc[pv-1]
            self._cur_move[4]=p
            self._cur_move[6]=self.PROMOTION_MOVE
        elif self._turn == self.BLACK and toPos[1] == 7:
            if pv == 0:
                self._reason = self.MUST_SET_PROMOTION
                return False
            pc = ['q', 'r', 'n', 'b']
            p = pc[pv-1]
            self._cur_move[4]=p
            self._cur_move[6]=self.PROMOTION_MOVE
        else:
            p = self._board[fromPos[1]][fromPos[0]]

        if t == self.EP_MOVE:
            self.setEP(toPos)
            self._cur_move[6]=self.EP_MOVE
        else:
            self.clearEP()

        if self._board[toPos[1]][toPos[0]] != '.':
            self._cur_move[3]=True

        self._board[toPos[1]][toPos[0]] = p
        self._board[fromPos[1]][fromPos[0]] = "."

        self._fifty = 0
        return True

    def moveKnight(self, fromPos, toPos):
        moves = self.getValidKnightMoves(fromPos)

        if not toPos in moves:
            return False

        self.clearEP()

        if self._board[toPos[1]][toPos[0]] == ".":
            self._fifty+=1
        else:
            self._fifty=0
            self._cur_move[3]=True

        self._board[toPos[1]][toPos[0]] = self._board[fromPos[1]][fromPos[0]]
        self._board[fromPos[1]][fromPos[0]] = "."
        return True

    def moveKing(self, fromPos, toPos):
        if self._turn == self.WHITE:
            c_row = 7
            k = "K"
            r = "R"
        else:
            c_row = 0
            k = "k"
            r = "r"

        moves, specialMoves = self.getValidKingMoves(fromPos)

        if specialMoves.has_key(toPos):
            t = specialMoves[toPos]
        else:
            t = 0

        if not toPos in moves:
            return False

        self.clearEP()

        if self._turn == self.WHITE:
            self._white_king_castle = False
            self._white_queen_castle = False
        else:
            self._black_king_castle = False
            self._black_queen_castle = False

        if t == self.KING_CASTLE_MOVE:
            self._fifty+=1
            self._board[c_row][4] = "."
            self._board[c_row][6] = k
            self._board[c_row][7] = "."
            self._board[c_row][5] = r
            self._cur_move[6] = self.KING_CASTLE_MOVE
        elif t == self.QUEEN_CASTLE_MOVE:
            self._fifty+=1
            self._board[c_row][4] = "."
            self._board[c_row][2] = k
            self._board[c_row][0] = "."
            self._board[c_row][3] = r
            self._cur_move[6] = self.QUEEN_CASTLE_MOVE
        else:
            if self._board[toPos[1]][toPos[0]] == ".":
                self._fifty+=1
            else:
                self._fifty=0
                self._cur_move[3]=True

            self._board[toPos[1]][toPos[0]] = self._board[fromPos[1]][fromPos[0]]
            self._board[fromPos[1]][fromPos[0]] = "."

        self.updateKingLocations()
        return True

    def moveQueen(self, fromPos, toPos):

        moves = self.getValidQueenMoves(fromPos)

        if not toPos in moves:
            return False

        self.clearEP()

        if self._board[toPos[1]][toPos[0]] == ".":
            self._fifty+=1
        else:
            self._fifty=0
            self._cur_move[3]=True

        self._board[toPos[1]][toPos[0]] = self._board[fromPos[1]][fromPos[0]]
        self._board[fromPos[1]][fromPos[0]] = "."
        return True

    def moveBishop(self, fromPos, toPos):
        moves = self.getValidBishopMoves(fromPos)

        if not toPos in moves:
            return False

        self.clearEP()

        if self._board[toPos[1]][toPos[0]] == ".":
            self._fifty+=1
        else:
            self._fifty=0
            self._cur_move[3]=True

        self._board[toPos[1]][toPos[0]] = self._board[fromPos[1]][fromPos[0]]
        self._board[fromPos[1]][fromPos[0]] = "."
        return True

    def moveRook(self, fromPos, toPos):

        moves = self.getValidRookMoves(fromPos)

        if not toPos in moves:
            return False

        fx, fy = fromPos
        if self._turn == self.WHITE:
            if fx == 0:
                self._white_queen_castle = False
            if fx == 7:
                self._white_king_castle = False
        if self._turn == self.BLACK:
            if fx == 0:
                self._black_queen_castle = False
            if fx == 7:
                self._black_king_castle = False

        self.clearEP()

        if self._board[toPos[1]][toPos[0]] == ".":
            self._fifty+=1
        else:
            self._fifty=0
            self._cur_move[3]=True

        self._board[toPos[1]][toPos[0]] = self._board[fromPos[1]][fromPos[0]]
        self._board[fromPos[1]][fromPos[0]] = "."
        return True

    def _parseTextMove(self, txt):

        txt = txt.strip()
        promotion = None
        dest_x = 0
        dest_y = 0
        h_piece = "P"
        h_rank = -1
        h_file = -1

        # handle the special
        if txt == "O-O":
            if self._turn == 0:
                return (None, 4, 7, 6, 7, None)
            if self._turn == 1:
                return (None, 4, 0, 6, 0, None)
        if txt == "O-O-O":
            if self._turn == 0:
                return (None, 4, 7, 2, 7, None)
            if self._turn == 1:
                return (None, 4, 0, 2, 0, None)

        files = {"a":0, "b":1, "c":2, "d":3, "e":4, "f":5, "g":6, "h":7}
        ranks = {"8":0, "7":1, "6":2, "5":3, "4":4, "3":5, "2":6, "1":7}

        # Clean up the textmove
        "".join(txt.split("e.p."))
        t = []
        for ch in txt:
            if ch not in "KQRNBabcdefgh12345678":
                continue
            t.append(ch)

        if len(t)<2:
            return None

        # Get promotion if any
        if t[-1] in ('Q', 'R', 'N', 'B'):
            promotion = {'Q':1, 'R':2, 'N':3, 'B':4}[t.pop()]

        if len(t)<2:
            return None

        # Get the destination
        if not files.has_key(t[-2]) or not ranks.has_key(t[-1]):
            return None

        dest_x = files[t[-2]]
        dest_y = ranks[t[-1]]

        # Pick out the hints
        t = t[:-2]
        for h in t:
            if h in ('K', 'Q', 'R', 'N', 'B', 'P'):
                h_piece = h
            elif h in ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'):
                h_file = files[h]
            elif h in ('1', '2', '3', '4', '5', '6', '7', '8'):
                h_rank = ranks[h]

        # If we have both a source and destination we don't need the piece hint.
        # This will make us make the move directly.
        if h_rank > -1 and h_file > -1:
            h_piece = None

        return (h_piece, h_file, h_rank, dest_x, dest_y, promotion)

    def _formatTextMove(self, move, format):
        #piece, from, to, take, promotion, check

        piece = move[0]
        fpos = tuple(move[1])
        tpos = tuple(move[2])
        take = move[3]
        promo = move[4]
        check = move[5]
        special = move[6]

        files = "abcdefgh"
        ranks = "87654321"
        if format == self.AN:
            res = "%s%s%s%s" % (files[fpos[0]], ranks[fpos[1]], files[tpos[0]], ranks[tpos[1]])
        elif format == self.LAN:

            if special == self.KING_CASTLE_MOVE:
                return "O-O"
            elif special == self.QUEEN_CASTLE_MOVE:
                return "O-O-O"

            tc = "-"
            if take:
                tc = "x"
            pt = ""
            if promo:
                pt = "=%s" % promo
            if piece == "P":
                piece = ""
            if not check:
                check = ""
            res = "%s%s%s%s%s%s%s%s" % (piece, files[fpos[0]], ranks[fpos[1]], tc, files[tpos[0]], ranks[tpos[1]], pt, check)
        elif format == self.SAN:

            if special == self.KING_CASTLE_MOVE:
                return "O-O"
            elif special == self.QUEEN_CASTLE_MOVE:
                return "O-O-O"

            tc = ""
            if take:
                tc = "x"
            pt = ""
            if promo:
                pt = "=%s" % promo.upper()
            p = piece
            if self._turn == self.BLACK:
                p = p.lower()
            if piece == "P":
                piece = ""
            if not check:
                check = ""
            fx, fy = fpos
            hint_f = ""
            hint_r = ""
            for y in range(8):
                for x in range(8):
                    if self._board[y][x] == p:
                        if x == fx and y == fy:
                            continue
                        vm = self.getValidMoves((x, y))
                        if tpos in vm:
                            if fx == x:
                                hint_r = ranks[fy]
                            else:
                                hint_f = files[fx]
            if piece == "" and take:
                hint_f = files[fx]
            res = "%s%s%s%s%s%s%s%s" % (piece, hint_f, hint_r, tc, files[tpos[0]], ranks[tpos[1]], pt, check)
        return res

    #----------------------------------------------------------------------------
    # PUBLIC METHODS
    #----------------------------------------------------------------------------

    def resetBoard(self):
        """
        Resets the chess board and all states.
        """
        self._board = [
            ['r', 'n', 'b', 'q', 'k', 'b', 'n', 'r'],
            ['p']*8,
            ['.']*8,
            ['.']*8,
            ['.']*8,
            ['.']*8,
            ['P']*8,
            ['R', 'N', 'B', 'Q', 'K', 'B', 'N', 'R']
            ]
        self._turn = self.WHITE
        self._white_king_castle = True
        self._white_queen_castle = True
        self._black_king_castle = True
        self._black_queen_castle = True
        self._ep = [0, 0]
        self._fifty = 0
        self._three_rep_stack = []
        self._state_stack = []
        self._moves = []
        self._reason = 0
        self._game_result = 0
        self.pushState()
        self.updateKingLocations()

    def setFEN(self, fen):
        """
        Sets the board and states accoring from a Forsyth-Edwards Notation string.
        Ex. 'rnbqkbnr/pp1ppppp/8/2p5/4P3/5N2/PPPP1PPP/RNBQKB1R b KQkq - 1 2'
        """
        self._three_rep_stack = []
        self._state_stack = []
        self._moves = []
        self._reason = 0
        self._game_result = 0

        fparts = fen.split()
        newstate = ""

        #BOARD
        for c in fparts[0]:
            if c in "kqrnbpKQRNBP":
                newstate += c
            elif c in "12345678":
                newstate += '.' * int(c)
        #TURN
        newstate += str("wb".index(fparts[1]))

        #CASTLING
        kq = "KQkq"
        for p in kq:
            if p in fparts[2]:
                newstate += "1"
            else:
                newstate += "0"

        #EN PASSANT
        if len(fparts[3]) == 2:
            newstate += str("abcdefgh".index(fparts[3][0].lower()))
            newstate += str("87654321".index(fparts[3][1]))
        else:
            newstate += "00"

        #GAME RESULT
        newstate+="0"

        #HALF COUNT
        newstate+=":%s" % fparts[4]

        self._state_stack.append(newstate)
        self._state_stack_pointer = 1
        self.loadCurState()

        three_state = [self._white_king_castle,
            self._white_queen_castle,
            self._black_king_castle,
            self._black_queen_castle,
            deepcopy(self._board),
            deepcopy(self._ep)]

        self._three_rep_stack.append(three_state)

        self.updateKingLocations()

    def getFEN(self):
        """
        Returns the current state as Forsyth-Edwards Notation string.
        """
        s = self._state_stack[self._state_stack_pointer-1]

        b= s[:64]
        v = s[64:72]
        fifty =  s[73:]

        rows = []
        for i in range(8):
            row = b[i*8:(i+1)*8]
            cnt = 0; res = ""
            for c in row:
                if c == ".":
                    cnt+=1
                else:
                    if cnt:
                        res += str(cnt);
                        cnt=0
                    res+=c
            if cnt:
                res += str(cnt)
            rows.append(res)
        board = "/".join(rows)

        turn = (["w", "b"])[int(v[0])]

        kq = ""
        if int(v[1]): kq+="K"
        if int(v[2]): kq+="Q"
        if int(v[3]): kq+="k"
        if int(v[4]): kq+="q"
        if not kq:
            kq = "-"

        x = int(v[5])
        y = int(v[6])
        ep = "-"
        if not (x == 0 and y == 0):
            if turn == "b" and (self._board[y][x-1] == 'p' or self._board[y][x+1] == 'p'):
                ep = "%s%s" % ( ("abcdefgh")[x], ("87654321")[y+1])
            elif turn == "w" and (self._board[y][x-1] == 'P' or self._board[y][x+1] == 'P'):
                ep = "%s%s" % ( ("abcdefgh")[x], ("87654321")[y-1])

        move = (self._state_stack_pointer+1)/2
        

        ## Arbitrary change

        return "%s %s %s %s %s %d" % (board, turn, kq, ep, fifty, move)

    def getMoveCount(self):
        """
        Returns the number of halfmoves in the stack.
        Zero (0) means no moves has been made.
        """
        return len(self._state_stack)-1

    def getCurrentMove(self):
        """
        Returns the current halfmove number. Zero (0) means before first move.
        """
        return self._state_stack-1

    def gotoMove(self, move):
        """
        Goto the specified halfmove. Zero (0) is before the first move.
        Return False if move is out of range.
        """
        move+=1
        if move > len(self._state_stack):
            return False
        if move < 1:
            return False

        self._state_stack_pointer = move
        self.loadCurState()

    def gotoFirst(self):
        """
        Goto before the first known move.
        """
        self._state_stack_pointer = 1
        self.loadCurState()

    def gotoLast(self):
        """
        Goto after the last knwon move.
        """
        self._state_stack_pointer = len(self._state_stack)
        self.loadCurState()

    def undo(self):
        """
        Undo the last move. Can be used to step back until the initial board setup.
        Returns True or False if no more moves can be undone.
        """
        if self._state_stack_pointer <= 1:
            return False
        self._state_stack_pointer -= 1
        self.loadCurState()
        return True

    def redo(self):
        """
        If you used the undo method to step backwards you can use this method to step forward until the last move i reached.
        Returns True or False if no more moves can be redone.
        """
        if self._state_stack_pointer == len(self._state_stack):
            return False
        self._state_stack_pointer += 1
        self.loadCurState()
        return True

    def setPromotion(self, promotion):
        """
        Tell the chessboard how to promote a pawn.
        1=QUEEN, 2=ROOK, 3=KNIGHT, 4=BISHOP
        You can also set promotion to 0 (zero) to reset the promotion value.
        """
        self._promotion_value = promotion

    def getPromotion(self):
        """
        Returns the current promotion value.
        1=QUEEN, 2=ROOK, 3=KNIGHT, 4=BISHOP
        """
        return self._promotion_value

    def isCheck(self):
        """
        Returns True if the current players king is checked.
        """
        if self._turn == self.WHITE:
            kx, ky = self._white_king_location
        else:
            kx, ky = self._black_king_location

        return self.isThreatened(kx, ky, self._turn)

    def isGameOver(self):
        """
        Returns True if the game is over by either checkmate or draw.
        """
        if self._game_result:
            return True
        return False

    def getGameResult(self):
        """
        Returns the reason for game over.
        It can be the following reasons: 1=WHITE_WIN , 2=BLACK_WIN, 3=STALEMATE, 4=FIFTY_MOVES_RULE,5=THREE_REPETITION_RULE.
        If game is not over this method returns zero(0).
        """
        return self._game_result

    def getBoard(self):
        """
        Returns a copy of the current board layout. Uppercase letters for white, lovercase for black.
        K=King, Q=Queen, B=Bishop, N=Night, R=Rook, P=Pawn.
        Empty squares are markt with a period (.)
        """
        return deepcopy(self._board)

    def getTurn(self):
        """
        Returns the current player. 0=WHITE, 1=BLACK.
        """
        return self._turn

    def getReason(self):
        """
        Returns the reason to why addMove returned False.
        1=INAVLID_MOVE,2=INVALID_COLOR,3=INVALID_FROM_LOCATION,4=INVALID_TO_LOCATION,5=MUST_SET_PROMOTION,5=GAME_IS_OVER
        """
        return self._reason

    def getValidMoves(self,location):
        """
        Returns a list of valid moves. (ex [ [3,4], [3, 5], [3, 6] ... ] ) If there isn't a valid piece on that location or the piece on the selected
        location hasn't got any valid moves an empty list is returned.
        The location argument must be a tuple containing an x, y value Ex. (3, 3)
        """
        if self._game_result:
            return []

        x, y = location

        if x < 0 or x > 7 or y < 0 or y > 7:
            return False

        self.updateKingLocations()

        if self.getColor(x, y) != self._turn:
            return []

        p = self._board[y][x].upper()
        if p == 'P':
            m, s = self.getValidPawnMoves(location)
            return m
        elif p == 'R':
            return self.getValidRookMoves(location)
        elif p == 'B':
            return self.getValidBishopMoves(location)
        elif p == 'Q':
            return self.getValidQueenMoves(location)
        elif p == 'K':
            m, s = self.getValidKingMoves(location)
            return m
        elif p == 'N':
            return self.getValidKnightMoves(location)
        else:
            return []

    def addMove(self, fromPos, toPos):
        """
        Tries to move the piece located om fromPos to toPos. Returns True if that was a valid move.
        The position arguments must be tuples containing x, y value Ex. (4, 6).
        This method also detects game over.

        If this method returns False you can use the getReason method to determin why.
        """
        self._reason = 0
        #                piece,from,to,take,promotion,check,specialmove
        self._cur_move = [None, None, None, False, None, None, self.NORMAL_MOVE]

        if self._game_result:
            self._result = self.GAME_IS_OVER
            return False

        self.updateKingLocations()

        fx, fy = fromPos
        tx, ty = toPos

        self._cur_move[1]=fromPos
        self._cur_move[2]=toPos

        #check invalid coordinates
        if fx < 0 or fx > 7 or fy < 0 or fy > 7:
            self._reason = self.INVALID_FROM_LOCATION
            return False

        #check invalid coordinates
        if tx < 0 or tx > 7 or ty < 0 or ty > 7:
            self._reason = self.INVALID_TO_LOCATION
            return False

        #check if any move at all
        if fx==tx and fy==ty:
            self._reason = self.INVALID_TO_LOCATION
            return False

        #check if piece on location
        if self.isFree(fx, fy):
            self._reason = self.INVALID_FROM_LOCATION
            return False

        #check color of piece
        if self.getColor(fx, fy) != self._turn:
            self._reason = self.INVALID_COLOR
            return False

        # Call the correct handler
        p = self._board[fy][fx].upper()
        self._cur_move[0]=p
        if p == 'P':
            if not self.movePawn((fx, fy), (tx, ty)):
                if not self._reason:
                    self._reason = self.INVALID_MOVE
                return False
        elif p == 'R':
            if not self.moveRook((fx, fy), (tx, ty)):
                self._reason = self.INVALID_MOVE
                return False
        elif p == 'B':
            if not self.moveBishop((fx, fy), (tx, ty)):
                self._reason = self.INVALID_MOVE
                return False
        elif p == 'Q':
            if not self.moveQueen((fx, fy), (tx, ty)):
                self._reason = self.INVALID_MOVE
                return False
        elif p == 'K':
            if not self.moveKing((fx, fy), (tx, ty)):
                self._reason = self.INVALID_MOVE
                return False
        elif p == 'N':
            if not self.moveKnight((fx, fy), (tx, ty)):
                self._reason = self.INVALID_MOVE
                return False
        else:
            return False

        if self._turn == self.WHITE:
            self._turn = self.BLACK
        else:
            self._turn = self.WHITE

        if self.isCheck():
            self._cur_move[5]="+"

        if not self.hasAnyValidMoves():
            if self.isCheck():
                self._cur_move[5]="#"
                if self._turn == self.WHITE:
                    self.endGame(self.BLACK_WIN)
                else:
                    self.endGame(self.WHITE_WIN)
            else:
                self.endGame(self.STALEMATE)
        else:
            if self._fifty == 100:
                self.endGame(self.FIFTY_MOVES_RULE)
            elif self.threeRepetitions():
                self.endGame(self.THREE_REPETITION_RULE)

        self.pushState()
        self.pushMove()

        return True

    def getLastMoveType(self):
        """
        Returns a value that indicates if the last move was a "special move".
        Returns -1 if no move has been done.
        Return value can be:
        0=NORMAL_MOVE
        1=EP_MOVE (Pawn is moved two steps and is valid for en passant strike)
        2=EP_CAPTURE_MOVE (A pawn has captured another pawn by using the en passant rule)
        3=PROMOTION_MOVE (A pawn has been promoted. Use getPromotion() to see the promotion piece.)
        4=KING_CASTLE_MOVE (Castling on the king side.)
        5=QUEEN_CASTLE_MOVE (Castling on the queen side.)
        """
        if self._state_stack_pointer<=1: # No move has been done at thos pointer
            return -1

        self.undo()
        move = self._moves[self._state_stack_pointer-1]
        res = move[6]
        self.redo()

        return res

    def getLastMove(self):
        """
        Returns a tuple containing two tuples describing the move just made using the internal coordinates.
        In the format ((from_x, from_y), (to_x, to_y))
        Ex. ((4, 6), (4, 4))
        Returns None if no moves has been made.
        """
        if self._state_stack_pointer<=1: # No move has been done at thos pointer
            return None

        self.undo()
        move = self._moves[self._state_stack_pointer-1]
        res = (move[1], move[2])
        self.redo()

        return res

    def addTextMove(self, txt):
        """
        Adds a move using several different standards of the Algebraic chess notation.
        AN Examples: 'e2e4' 'f1d1' 'd7-d8' 'g1-f3'
        SAN Examples: 'e4' 'Rfxd1' 'd8=Q' 'Nxf3+'
        LAN Examples: 'Pe2e4' 'Rf1xd1' 'Pd7d8=Q' 'Ng1xf3+'
        """
        res = self._parseTextMove(txt)
        if not res:
            self._reason = self.INVALID_MOVE
            return False
        else:
            piece, fx, fy, tx, ty, promo = res

        if promo:
            self.setPromotion(promo)

        if not piece:
            return self.addMove((fx, fy), (tx, ty))

        if self._turn == self.BLACK:
            piece = piece.lower()

        move_to = None
        move_from = None
        found_move = False
        for y in range(8):
            for x in range(8):
                if self._board[y][x] == piece:
                    if fx > -1 and fx != x:
                        continue
                    if fy > -1 and fy != y:
                        continue
                    vm = self.getValidMoves((x, y))
                    for m in vm:
                        if m[0] == tx and m[1] == ty:
                            if found_move:
                                self._reason = self.AMBIGUOUS_MOVE
                                return False
                            found_move = True
                            move_from = (x, y)
                            move_to = (tx, ty)

        if found_move:
            return self.addMove(move_from, move_to)

        self._reason = self.INVALID_MOVE
        return False

    def getAllTextMoves(self, format=1):
        """
        Returns a list of all moves done so far in Algebraic chess notation.
        Returns None if no moves has been made.
        """
        if self._state_stack_pointer<=1: # No move has been done at this pointer
            return None

        res = []

        point = self._state_stack_pointer

        self.gotoFirst()
        while True:
            move = self._moves[self._state_stack_pointer-1]
            res.append(self._formatTextMove(move, format))
            if self._state_stack_pointer >= len(self._state_stack)-1:
                break
            self.redo()

        self._state_stack_pointer = point
        self.loadCurState()

        return res

    def getLastTextMove(self, format=1):
        """
        Returns the latest move as Algebraic chess notation.
        Returns None if no moves has been made.
        """
        if self._state_stack_pointer<=1: # No move has been done at this pointer
            return None

        self.undo()
        move = self._moves[self._state_stack_pointer-1]
        res = self._formatTextMove(move, format)
        self.redo()
        return res

   
